package xin.javashare.sort;

/**
 * 程序清单24.5【归并排序】
 * 时间复杂度O(nlogn),优于选择排序，插入排序，冒泡排序
 * java.util.Arrays类中的sort方法，是使用归并排序的变体来实现的
 * 最差情况下，效率高于快速排序，但平均情况下效率相同。
 * <p>
 * 在归并两个子数组时，需要一个临时数组，空间效率低于快速排序，堆排序
 */
public class MergeSort {
    public static void mergeSort(int[] list) {
        if (list.length > 1) {
            int[] firstHalf = new int[list.length / 2];
            System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
            mergeSort(firstHalf);

            int secondHalfLength = list.length - list.length / 2;
            int[] secondHalf = new int[secondHalfLength];
            System.arraycopy(list, list.length / 2, secondHalf, 0, secondHalfLength);
            mergeSort(secondHalf);

            int[] temp = merge(firstHalf, secondHalf);
            System.arraycopy(temp, 0, list, 0, temp.length);
        }
    }

    private static int[] merge(int[] list1, int[] list2) {
        int[] temp = new int[list1.length + list2.length];

        int current1 = 0;
        int current2 = 0;
        int current3 = 0;

        while (current1 < list1.length && current2 < list2.length) {
            if (list1[current1] < list2[current2])
                temp[current3++] = list1[current1++];
            else
                temp[current3++] = list2[current2++];
        }

        while (current1 < list1.length) {
            temp[current3++] = list1[current1++];
        }

        while (current2 < list2.length) {
            temp[current3++] = list2[current2++];
        }

        return temp;
    }

    public static void main(String[] args) {
        int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        mergeSort(list);
        for (int i = 0; i < list.length; i++) {
            System.out.print(list[i] + " ");
        }
    }
}
